package com.hooper.solution.day11;

/**
 * @author Tim Hooper
 * @version 1.0
 * @time 2023/02/19/22:23
 */
public class Solutions {

    /**
     * 给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
     * 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
     * 你可以假设除了整数 0 之外，这个整数不会以零开头。
     * 示例：
     * 输入：digits = [1,2,3]
     * 输出：[1,2,4]
     * 解释：输入数组表示数字 123。
     * 示例2：
     * 输入：digits = [4,3,2,1]
     * 输出：[4,3,2,2]
     * 解释：输入数组表示数字 4321。
     * 示例 3：
     * 输入：digits = [0]
     * 输出：[1]
     * <p>
     * 提示：
     * 1 <= digits.length <= 100
     * 0 <= digits[i] <= 9
     */
    public static int[] plusOne(int[] digits) {
        int len = digits.length;
        boolean isNine = digits[len - 1] == 9;
        //若个位数不为9直接+1返回
        if (!isNine) {
            ++digits[len - 1];
            return digits;
        }
        int j = len - 1;
        for (int i = len - 1; i >= 0; i--) {
            if (i != j) break;

            if (++digits[i] == 10) {
                j--;
                digits[i] = 0;
            } else break;
        }
        if (digits[0] == 0) {
            int[] res = new int[len + 1];
            res[0] = 1;
            return res;
        }
        return digits;
    }

    /**
     * 69. x 的平方根
     * 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
     * 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
     * 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
     * 示例 1：
     * 输入：x = 4
     * 输出：2
     * 示例 2：
     * 输入：x = 8
     * 输出：2
     * 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
     */
    public static int mySqrt(int x) {
        if (x < 4) return x == 0 ? 0 : 1;
        int left = 1;
        int right = x;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            long pre = (long) mid * (long) mid;
            long last = (long) (mid + 1) * (mid + 1);
            if (x >= pre && x < last) {
                return mid;
            } else if (x > last) {
                left = mid;
            } else if (x < pre) {
                right = mid + 1;
            } else if (x == last) {
                return mid + 1;
            }
        }
        return left;
    }
}
